package com.pan.games.leecode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author by panstark
 * @description
 * @notice
 * @date 2021/4/8
 */
public class SpiralOrder {

    public static void main(String[] args) {
        SpiralOrder s = new SpiralOrder();
//        int[][] aa = new int[][]{{1,1}};
//        s.spiralOrder(aa);
        int[] coo = new int[]{-2,1,-1,-2};
        s.asteroidCollision(coo);

    }
    public int[] spiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return new int[0];
        }

        int rows = matrix.length;
        int colums = matrix[0].length;
        int[][] directions = {{0,1},{1,0},{0,-1},{-1,0}};
        boolean[][] visted = new boolean[rows][colums];
        int total = rows*colums;
        int[] order =  new int[total];
        int curRow = 0,curColum=0;
        int directionIndex = 0;
        for (int i = 0; i < total; i++) {
            order[i] = matrix[curRow][curColum];
            visted[curRow][curColum] = true;
            int nextRow = curRow+directions[directionIndex][0];
            int nextColum = curColum+directions[directionIndex][1];
            if(nextRow<0||nextRow>=rows||nextColum<0||nextColum>=colums||visted[nextRow-1][nextColum-1]){
                directionIndex = (directionIndex+1)%4;
            }

            curRow += directions[directionIndex][0];
            curColum += directions[directionIndex][1];

        }

        return order;

    }

    public TreeNode getTreeNode(){
        TreeNode tn= new TreeNode();
        tn.val=1;
        TreeNode left = new TreeNode();
        left.val=2;
        tn.left = left;
        return tn;
    }


    /**
     * 行星碰撞
     *
     */
    public int[] asteroidCollision(int[] asteroids) {
        if(asteroids==null||asteroids.length==0){
            return new int[0];
        }
        List<Integer> neverCollision = new ArrayList<>();
        Stack<Integer> collision = new Stack<>();
        boolean firstLeft = true;
        for (int i = 0; i < asteroids.length; i++) {

            int asteroids1 = asteroids[i];
            if(asteroids1<0){
                if(firstLeft){
                    neverCollision.add(asteroids1);
                }else{
                    collise(asteroids1,collision);
                }
            }else{
                firstLeft=false;
                collision.push(asteroids1);
            }
        }

        Stack<Integer> revers = new Stack<>();
        int num = collision.size();
        for (int i = 0; i < num; i++) {
            revers.push(collision.pop());
        }
        for (int i = 0; i < num; i++) {
            neverCollision.add(revers.pop());
        }
        int[] result = new int[neverCollision.size()];
        for (int i = 0; i < neverCollision.size(); i++) {
            result[i]=neverCollision.get(i);
            System.out.println("result"+i+","+result[i]);
        }
        return result;

    }

    private void collise(int asteroids1, Stack<Integer> collision) {
        if(collision.isEmpty()){
            collision.push(asteroids1);
            return;
        }
        int size = collision.size();

        for (int i=0;i<size;i++) {
            Integer integer = collision.peek();
            if((asteroids1<0&&integer<0)||(asteroids1>0&&integer>0)||(integer<0&&asteroids1>0)){
                collision.push(asteroids1);
                break;
            }else{
               if(Math.abs(asteroids1)>Math.abs(integer)) {
                   collision.pop();
                   if(collision.isEmpty()){
                       collision.push(asteroids1);
                   }
               }else if(Math.abs(asteroids1)==Math.abs(integer)){
                   collision.pop();
                   break;
               }else{
                   break;
               }
            }
        }
    }


}
